// // 有序list的斐波那契查找, hzsong123, 2024-0226
// // 斐波那契查找: https://blog.csdn.net/fovwin/article/details/9077017
// // https://github.com/AASF-IIITM/algorithms/blob/master/Java/FibonacciSearch.java

// // use super::ordered_i32::IOrdered32;



// /*  Precomputed Fibonacci numbers F0 up to F46. This implementation assumes that the size n
// *  of the input array fits in 4 bytes. Note that F46=1836311903 is the largest Fibonacci
// *  number that is less or equal to the 4-byte INT_MAX (=2147483647). The next Fibonacci
// *  number, i.e. F47, is 2971215073 and is larger than INT_MAX, implying that it does not
// *  fit in a 4 byte integer. Note also that the last array element is INT_MAX rather than
// *  F47. This ensures correct operation for n>F46.
// */
// const FB_INDICES: [usize; 47] = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34,
//     55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181,
//     6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229,
//     832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986,
//     102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903];

// /*
//   Fibonaccian search for locating the index of "key" in an array "pData" of size "n"
//   that is sorted in ascending order. See http://doi.acm.org/10.1145/367487.367496

//   Algorithm description
//   -----------------------------------------------------------------------------
//   Let Fk represent the k-th Fibonacci number where Fk+2=Fk+1 + Fk for k>=0 and
//   F0 = 0, F1 = 1. To test whether an item is in a list of n = Fm ordered numbers,
//   proceed as follows:
//   a) Set k = m.
//   b) If k = 0, finish - no match.
//   c) Test item against entry in position Fk-1.
//   d) If match, finish.
//   e) If item is less than entry Fk-1, discard entries from positions Fk-1 + 1 to n.
//      Set k = k - 1 and go to b).
//   f) If item is greater than entry Fk-1, discard entries from positions 1 to Fk-1.
//      Renumber remaining entries from 1 to Fk-2, set k = k - 2 and go to b)

//   If Fm>n then the original array is augmented with Fm-n numbers larger
//   than key and the above algorithm is applied.
//  */
// pub fn index_of<V>(items: &Vec<V>, key2find: i32) -> Option<usize>
//     where V: IOrdered32 {
//     let len = items.len();
//     let mut i_left = 0; // (m-2)'th Fibonacci No. 
//     let mut i_mid = 1; // (m-1)'th Fibonacci No. 
//     let mut i_right = i_left + i_mid; // m'th Fibonacci 

//     loop {
//         if i_right > len {
//             break;
//         }
//         i_left = i_mid; 
//         i_mid = i_right; 
//         i_right = i_left + i_mid;
//     }


//     let mut offset_opt: Option<usize> = None; 

//     let mut index = 0;
//     loop {
//         if i_right <= 1 {
//             break;
//         }
//         index = match offset_opt {
//             Some(offset) => (i_left + offset).min(len - 1),
//             None => (i_left - 1).min(len - 1),
//         };
        
//         let key = items[index].key();
//         if key == key2find {
//             return Some(index);
//         }
//         if key < key2find {
//             i_right = i_mid; 
//             i_mid = i_left; 
//             i_left = i_right - i_mid; 
//             offset_opt = Some(index); 
//         } else {
//             // if key > key2find
//             i_right = i_left; 
//             i_mid = i_mid - i_left; 
//             i_left = i_right - i_mid; 
//         }
        
//     }
//     index = match offset_opt {
//         Some(offset) => offset + 1,
//         None => 0,
//     };

//     let key = items[index].key();
//     if i_mid == 1 && key == key2find {
//         return Some(index); 
//     }


//     None
// }


// pub fn index_of_list32(items: &Vec<i32>, key2find: i32) -> Option<usize>  {
//     let len = items.len();
//     let mut i_left = 0; // (m-2)'th Fibonacci No. 
//     let mut i_mid = 1; // (m-1)'th Fibonacci No. 
//     let mut i_right = i_left + i_mid; // m'th Fibonacci 

//     loop {
//         if i_right > len {
//             break;
//         }
//         i_left = i_mid; 
//         i_mid = i_right; 
//         i_right = i_left + i_mid;
//     }


//     let mut offset_opt: Option<usize> = None; 

//     let mut index = 0;
//     loop {
//         if i_right <= 1 {
//             break;
//         }
//         index = match offset_opt {
//             Some(offset) => (i_left + offset).min(len - 1),
//             None => (i_left - 1).min(len - 1),
//         };
        
//         let key = items[index];
//         if key == key2find {
//             return Some(index);
//         }
//         if key < key2find {
//             i_right = i_mid; 
//             i_mid = i_left; 
//             i_left = i_right - i_mid; 
//             offset_opt = Some(index); 
//         } else {
//             // if key > key2find
//             i_right = i_left; 
//             i_mid = i_mid - i_left; 
//             i_left = i_right - i_mid; 
//         }
        
//     }
//     index = match offset_opt {
//         Some(offset) => offset + 1,
//         None => 0,
//     };

//     let key = items[index];
//     if i_mid == 1 && key == key2find {
//         return Some(index); 
//     }


//     None
// }

// #[cfg(test)]
// mod tests {
//     use fasttime::b2_time::TimeFT;

//     use crate::list::ordered_i32::IOrdered32;

//     impl IOrdered32 for i32 {
//         fn key(&self) -> i32 {
//             *self
//         }
//     }

    
//     #[test]
//     fn test_fibonaccian_search_1() {
//         let name = "test_fibonaccian_search 普通单元测试";
//         let cpu = "Intel(R) Xeon(R) CPU E5 2680 v3 @ 2.50GHz 2.50GHz";
//         println!("{name}: {cpu}");
//         for count in [10_0000, 100_0000, 1000_0000, 1_0000_0000, 10_0000_0000] {
//             let time_开始 = TimeFT::now();
//             let mut items = Vec::with_capacity(count as usize);
//             for v in 0..count {
//                 items.push(v);
//             }
//             let time_初始化 = TimeFT::now();
//             for key2find in 0..count {
//                 match super::index_of_list32(&items, key2find) {
//                     Some(index) => assert_eq!(index as i32, key2find),
//                     None => panic!("{name} 必须找到: {key2find} [0, {count})"),
//                 }
//             }
//             let time_查找 = TimeFT::now();
//             let secs_初始化 = time_初始化.seconds_from(&time_开始);
//             let secs_查找 = time_查找.seconds_from(&time_初始化);
//             let micros_每一次查找 = time_查找.micros_from(&time_初始化) as f64 / count as f64;
//             println!("\t[0, {count}): {time_开始}, {secs_初始化:.3} 秒(初始化), {secs_查找:.3} 秒(查找), 平均 {micros_每一次查找:.1} 微秒 / 每一次查找.");
//         }
//         /*
//         cargo test test_fibonaccian_search_1 -- --nocapture
//         test_fibonaccian_search 普通单元测试: Intel(R) Xeon(R) CPU E5 2680 v3 @ 2.50GHz 2.50GHz
//         [0, 100000): 21:26:07(363)672, 0.004 秒(初始化), 0.077 秒(查找), 平均 0.8 微秒 / 每一次查找.
//         [0, 1000000): 21:26:07(444)683, 0.016 秒(初始化), 0.925 秒(查找), 平均 0.9 微秒 / 每一次查找.
//         [0, 10000000): 21:26:08(386)647, 0.156 秒(初始化), 10.933 秒(查找), 平均 1.1 微秒 / 每一次查找.
//         [0, 100000000): 21:26:19(480)422, 1.695 秒(初始化), 123.803 秒(查找), 平均 1.2 微秒 / 每一次查找.
//          */
//     }

    
//     #[test]
//     fn test_fibonaccian_search_2_最普通() {
//         let name = "test_fibonaccian_search_2_最普通 普通单元测试";
//         let cpu = "Intel(R) Xeon(R) CPU E5 2680 v3 @ 2.50GHz 2.50GHz";
//         println!("{name}: {cpu}");
//         for count in [10_0000, 100_0000, 1000_0000, 1_0000_0000, 10_0000_0000] {
//             let time_开始 = TimeFT::now();
//             let mut items = Vec::with_capacity(count as usize);
//             for v in 0..count {
//                 items.push(v);
//             }
//             let time_初始化 = TimeFT::now();
//             for key2find in 0..count {
//                 match super::index_of_list32(&items, key2find) {
//                     Some(index) => assert_eq!(index as i32, key2find),
//                     None => panic!("{name} 必须找到: {key2find} [0, {count})"),
//                 }

//             }
//             let time_查找 = TimeFT::now();
//             let secs_初始化 = time_初始化.seconds_from(&time_开始);
//             let secs_查找 = time_查找.seconds_from(&time_初始化);
//             let micros_每一次查找 = time_查找.micros_from(&time_初始化) as f64 / count as f64;
//             println!("\t[0, {count}): {time_开始}, {secs_初始化:.3} 秒(初始化), {secs_查找:.3} 秒(查找), 平均 {micros_每一次查找:.2} 微秒 / 每一次查找.");
//         }
//         /*
//         cargo test test_fibonaccian_search_2_最普通 -- --nocapture
//         test_binary_search_2_最普通 普通单元测试: Intel(R) Xeon(R) CPU E5 2680 v3 @ 2.50GHz 2.50GHz
//         [0, 100000): 21:32:47(817)358, 0.004 秒(初始化), 0.023 秒(查找), 平均 0.23 微秒 / 每一次查找.
//         [0, 1000000): 21:32:47(844)710, 0.016 秒(初始化), 0.289 秒(查找), 平均 0.29 微秒 / 每一次查找.
//         [0, 10000000): 21:32:48(149)775, 0.157 秒(初始化), 3.460 秒(查找), 平均 0.35 微秒 / 每一次查找.
//         [0, 100000000): 21:32:51(770)811, 1.724 秒(初始化), 36.398 秒(查找), 平均 0.36 微秒 / 每一次查找.
//         [0, 1000000000): 21:33:29(928)741, 16.607 秒(初始化), 395.831 秒(查找), 平均 0.40 微秒 / 每一次查找.
//          */
//     }
    
// }
